home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-estrin-sdrp-01.txt < prev    next >
Text File  |  1993-03-03  |  43KB  |  988 lines
  1.  
  2.  
  3. Network Working Group                                 Deborah Estrin
  4. INTERNET DRAFT                                                   USC
  5.                                                              Tony Li
  6.                                                        cisco Systems
  7.                                                        Yakov Rekhter
  8.                               T.J. Watson Research Center, IBM Corp.
  9.                                                             10/10/92
  10.                                                        Revision 0.93
  11.                                            Expiration Date: 04/10/92 
  12.  
  13.  
  14.        Source Demand Routing Protocol Specification (Version 1).
  15.  
  16.  
  17. Status of this Memo
  18.  
  19.    This document defines an inter-autonomous system routing protocol for
  20.    the Internet. This document specifies an IAB standards track protocol for
  21.    the Internet community, and requests discussion and suggestions for
  22.    improvements.  Please refer to the current edition of the "IAB
  23.    Official Protocol Standards" for the standardization state and status
  24.    of this protocol.  Distribution of this document is unlimited.
  25.  
  26.    This document is an Internet Draft. Internet Drafts are working
  27.    documents of the Internet Engineering Task Force (IETF), its Areas,
  28.    and its Working Groups. Note that other groups may also distribute
  29.    working documents as Internet Drafts.
  30.  
  31.    Internet Drafts are draft documents valid for a maximum of six
  32.    months.  Internet Drafts may be updated, replaced, or obsoleted by
  33.    other documents at any time. It is not appropriate to use Internet
  34.    Drafts as reference material or to cite them other than as a "working
  35.    draft" or "work in progress".
  36.  
  37.  
  38. 1 Overview
  39.  
  40.  
  41.    The purpose of SDRP is to support source-initiated selection of
  42.    inter-domain routes to complement the intermediate-node route
  43.    selection provided by BGP ([1], [2], [3]) or IDRP ([4]). This
  44.    document refers to such source-initiated routes as "SDRP routes".
  45.  
  46.    The protocol makes minimal assumptions about the distribution and
  47.    acquisition of routing information needed to construct the SDRP
  48.    routes.  These minimal assumptions are believed to be sufficient for
  49.    the existing Internet. Future versions of the protocol will extend
  50.    capabilities in this area and others in a largely backward-compatible
  51.    manner.
  52.  
  53.    This version of the protocol sends all packets with the complete SDRP
  54.    route in the SDRP header. Future versions will address route setup
  55.    and other enhancements and optimizations.
  56.  
  57.  
  58.  
  59.  
  60.  
  61. 2 Model of operations
  62.  
  63.  
  64.    An Internet can be viewed as a collection of routing domains
  65.    interconnected by means of common Layer 2 (Data Link Layer)
  66.    subnetworks, and Border Routers (BRs) attached to these subnetworks.
  67.    A BR belongs to only one domain. A pair of BRs, each belonging to a
  68.    different domain, but attached to a common subnetwork, form an
  69.    inter-domain connection. By definition, packets that traverse
  70.    multiple domains must traverse BRs of these domains.  Note that a
  71.    single physical router may act as multiple BRs for the purposes of
  72.    this model.
  73.  
  74.    A pair of domains is said to be adjacent if there is at least one
  75.    pair of BRs, one in each domain, that form an inter-domain
  76.    connection.
  77.  
  78.    Each domain has a globally unique identifier, called a Domain
  79.    Identifier (DI). All the BRs within a domain need to know the DI
  80.    assigned to the domain.  Management of the DI space is outside the
  81.    scope of this document.  This document assumes that Autonomous System
  82.    (AS) numbers are used as DIs.  Further, a domain path (or simply
  83.    path) in this document refers to a list of DIs as taken from a BGP AS
  84.    path or an IDRP RD path. We refer to a route as the combination of a
  85.    network address and a domain path. The network addresses are
  86.    represented by NLRI (Network Layer Reachability Information) as
  87.    described in [3].
  88.  
  89.    This document assumes that routing domains are congruent to the
  90.    autonomous systems. Thus, within the content of this document terms
  91.    autonomous system and routing domain can be used interchangeably.
  92.  
  93.    An SDRP route is defined as a sequence of domains, syntactically
  94.    expressed as a sequence of DIs (autonomous system numbers).
  95.  
  96.    Each SDRP route has a flag associated with it indicating whether it
  97.    is strict or loose.  A strict SDRP route means that any pair of
  98.    consecutive DI entries in the SDRP route must represent a pair of
  99.    adjacent domains.  A loose SDRP route may also allow a pair of
  100.    consecutive DI entries in the SDRP route to be separated by other
  101.    domains that are not listed in the route.
  102.  
  103.    It is assumed that a BR participates in the intra-domain routing
  104.    protocol(s) (IGPs) of the domain to which the BR belongs. Thus, a BR
  105.    may forward a packet to any other BR in its own domain using intra-
  106.    domain routing procedures.  Forwarding a packet between two BRs that
  107.    form an inter-domain connection requires neither the intra-domain nor
  108.    the inter-domain routing procedures (an inter-domain connection is a
  109.    common Layer 2 subnetwork).
  110.  
  111.    While SDRP does not require that all domains have a common network
  112.    layer protocol, all the BRs across the domains spanning a given SDRP
  113.    route are required to support a common network layer.  This document
  114.    specifies SDRP operations when that common network layer protocol is
  115.    IP ([5]).
  116.  
  117.    While this document requires all the BRs to support IP, the document
  118.    does not preclude a BR from additionally supporting other network
  119.    layer protocols as well (e.g., CLNP, IPX, AppleTalk).  If a BR
  120.    supports multiple network layers, then for the purposes of this
  121.    model, the BR must maintain multiple Forwarding Information Bases
  122.    (FIBs), one per network layer.
  123.  
  124.    Forwarding an IP packet along an SDRP route is accomplished by
  125.    encapsulating the packet in an SDRP packet.  An SDRP packet consists
  126.    of the SDRP header followed by the SDRP data.  The SDRP header
  127.    carries the SDRP route constructed by the domain that originated the
  128.    SDRP packet.  The SDRP data carries the original packet that the
  129.    source domain decided to forward via SDRP.
  130.  
  131.    An SDRP packet is carried across domains as the data portion of an IP
  132.    packet with protocol number 42.
  133.  
  134.    This document refers to the IP header of a packet that carries an
  135.    SDRP packet as the delivery IP header (or just the delivery header).
  136.    This document refers to the packet carried as SDRP data as the
  137.    payload packet, and the network layer header of the payload packet is
  138.    the payload header.
  139.  
  140.    Thus, an SDRP Packet can be represented as follows:
  141.  
  142.      +-------------------+--------------+-------------------
  143.      | Delivery header   |  SDRP header |  SDRP data
  144.      |    (IP header)    |              | (Payload packet)
  145.      +-------------------+--------------+--------------------
  146.  
  147.    Each SDRP route may have an MTU associated with it. An MTU of an SDRP
  148.    route is defined as the maximum length of the payload packet that can
  149.    be carried without fragmentation of an SDRP packet.  Procedures for
  150.    MTU discovery are specified in Section 9.
  151.  
  152.    It is assumed that a BR participates in either BGP or IDRP.  A BR
  153.    participating in SDRP augments its FIBs with a D-FIB that contains
  154.    routes to domains.  A route to a domain is a tuple that consists of a
  155.    destination domain (expressed as a DI), and the network layer address
  156.    of the next-hop BR.  D-FIBs are constructed based on the information
  157.    obtained from either BGP, IDRP, or configuration information.
  158.  
  159.    An SDRP packet is forwarded across multiple domains by utilizing the
  160.    forwarding databases (both FIBs and D-FIBs) maintained by the BRs.
  161.  
  162.    The operational status of SDRP routes is monitored via passive (Error
  163.    Reporting) and active (Route Probing) mechanisms. The Error Reporting
  164.    mechanism provides the originator of the SDRP route with a failure
  165.    notification.  The Probing mechanism provides the originator of the
  166.    SDRP route with confirmation of a route's feasibility.
  167.  
  168.  
  169. 3 SDRP Packet format
  170.  
  171.  
  172.    The total length of an SDRP packet (header plus data) can be
  173.    determined >from the information carried in the delivery IP header.
  174.    The length of the payload packet can be determined from the total
  175.    length of an SDRP packet and the length of its SDRP Header.
  176.  
  177.    The following describes the format of an SDRP packet.
  178.  
  179.    For a data packet:
  180.  
  181.        0                   1                   2                   3
  182.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  183.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  184.       | Ver |S|P|D|   |  BR Hop Count |SourceProtoType|  Payload Type |
  185.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  186.       |                    Source Route Identifier                    |
  187.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  188.       |                            Prefix                     |
  189.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  190.       |  PrefixLength |SrcRouteLength | NextDomainPtr | Source Route ...
  191.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  192.       |                           Payload ....
  193.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  194.  
  195.    For a control packet:
  196.  
  197.        0                   1                   2                   3
  198.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  199.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  200.       | Ver |S|P|D|   |  Notification |SourceProtoType|  Payload Type |
  201.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  202.       |                    Source Route Identifier                    |
  203.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  204.       |                     Target Border Router                      |
  205.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  206.       |                            Prefix                             |
  207.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  208.       |  PrefixLength |SrcRouteLength | NextDomainPtr | Source Route ...
  209.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  210.       |                           Payload ....
  211.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  212.  
  213.       Version and Flags  (1 octet)
  214.  
  215.       The SDRP version number and control flags are coded in the first
  216.       octet.  Bit 0 is the most significant bit, bit 7 is the least
  217.       significant bit.
  218.  
  219.          Version (bits 0 though 2)
  220.  
  221.             The first three bits  contain the Version field indicating
  222.             the version number of the protocol.  The value of this field
  223.             is set to 1.
  224.  
  225.          Flags (bits 3 through 7)
  226.  
  227.             Loose/Strict Source Route (bit 3)
  228.  
  229.                The Loose/Strict Source Route indicator is used when
  230.                making a forwarding decision (see Section 5.2).  If this
  231.                bit is set to 1, it indicates a Strict Source Route.  If
  232.                this bit is set to 0, it indicates a Loose Source Route.
  233.  
  234.             Probe Indicator (bit 4)
  235.  
  236.                The Probe Indicator is used by the originator of the
  237.                route to request verification of the route's feasibility
  238.                (see Sections 4 and 7.1).  If this bit is set to 1, it
  239.                indicates that the originator is probing the route.
  240.  
  241.             Data packet/Control packet (bit 5)
  242.  
  243.                If the bit is set to 1, then the packet carries data.
  244.                Otherwise, the packet carries control information.
  245.  
  246.             The rest of the Flags field is transmitted as zero, and
  247.             should be ignored on receipt.
  248.  
  249.       BR Hop Count (1 octet)
  250.  
  251.          This field is present only in data packets.
  252.  
  253.          The BR Hop Count field carries the maximum number of BRs an
  254.          SDRP data packet may traverse. It is decremented by 1 as an
  255.          SDRP data packet traverses a BR. Once the BR Hop Count field
  256.          reaches the value of 0, the BR should discard the data packet
  257.          and generate a control packet (see Section 5.2.4).
  258.  
  259.       Notification Code (1 octet)
  260.  
  261.             This field is present only in control packets.
  262.  
  263.             This document defines the following values for the
  264.             Notification Code:
  265.  
  266.                1 - No Route Available
  267.  
  268.                2 - Strict Source Route Failed
  269.  
  270.                3 - Transit Policy Violation
  271.  
  272.                4 - BR Hop Count Exceeded
  273.  
  274.                5 - Probe Completed
  275.  
  276.                6 - Unimplemented SDRP version
  277.  
  278.       Source Route Protocol Type (1 octet)
  279.  
  280.          The Source Route Protocol Type fields indicates the type of
  281.          Domain Identifiers (DIs) that appear in the source route.  The
  282.          value 1 in this field indicates that the DIs are Internet
  283.          Autonomous System numbers.
  284.  
  285.       Payload Protocol Type (1 octet)
  286.  
  287.          The Payload Protocol Type field indicates the protocol type of
  288.          the payload.  If the payload is an IP datagram, then this field
  289.          should contain the value 1.
  290.  
  291.       Source Route Identifier (4 octets)
  292.  
  293.          The BR  that originates the SDRP packet should insert a 32 bit
  294.          value in this field which will serve as an identifier for the
  295.          source route.  This value needs to be  unique  only in the
  296.          context of the originating BR.
  297.  
  298.       Target Border Router (4 octets)
  299.  
  300.          This field is present only in control packets.
  301.  
  302.          The Target Border Router contains one of the IP addresses of
  303.          the BR originating the SDRP packet that triggered the control
  304.          packet to be returned.
  305.  
  306.       Reserved (3 octets)
  307.  
  308.          This field is reserved for future use.
  309.  
  310.       Prefix (4 octets)
  311.  
  312.          The Prefix field contains an IP address prefix.  Only the
  313.          number of bits specified in the Prefix Length are significant.
  314.          The Prefix field is used to prevent routing loops when using
  315.          BGP or IDRP to route to the next AS in a loose source route
  316.          (see Section 4).
  317.  
  318.       Prefix Length (1 octet)
  319.  
  320.          The Prefix Length field indicates the length in bits of the IP
  321.          address prefix.  A length of zero indicates a prefix that
  322.          matches all IP addresses.
  323.  
  324.       Source Route Length (1 octet)
  325.  
  326.          The Source Route Length field indicates the length in octets of
  327.          the domain level source route carried in the SDRP Header.
  328.  
  329.       Next Domain Pointer (1 octet)
  330.  
  331.          The Next Domain Pointer field indicates the offset of the
  332.          high-order byte of the next domain identifier along the route
  333.          that the packet has to be forwarded.  This offset is relative
  334.          to the start of the Source Route field; so if the value of the
  335.          Next Domain Pointer field equals the value of the Source Route
  336.          Length field, then the entire source route has been completed.
  337.          All other source routes are said to be incomplete.
  338.  
  339.       Source Route (variable)
  340.  
  341.          Contains a sequence of domain identifiers (expressed as
  342.          Autonomous System numbers) that determines the sequence of
  343.          domains to be traversed. Each autonomous system is encoded as 2
  344.          octets.
  345.  
  346.       Payload (variable)
  347.  
  348.          The Payload field carries the datagram originated by the end-
  349.          system within the domain that constructed the SDRP packet. The
  350.          Payload field forms the data portion of the SDRP packet.  In a
  351.          control packet this field may be empty or may carry the payload
  352.          header of the packet that triggered the control message (see
  353.          5.2.5).  Note that there is no padding between the Source Route
  354.          and the Payload, and that the Payload may start at any
  355.          arbitrary octet boundary.
  356.  
  357.  
  358.  
  359.  
  360.  
  361. 4 Originating SDRP Data packets
  362.  
  363.  
  364.    This document assumes that a BR that originates SDRP packets is
  365.    preconfigured with a set of SDRP routes.  Procedures for constructing
  366.    these routes are outside the scope of this document.  It is assumed
  367.    that a BR has sufficient information to ascertain whether an IP
  368.    datagram received by the BR was originated by a host within the
  369.    domain the BR belongs to.  Procedures for acquiring this information
  370.    are outside of the scope of this document.
  371.  
  372.    When a BR receives an IP datagram originated by a host within its
  373.    domain, the BR uses the information in the datagram and the local
  374.    criteria to determine whether the datagram should be forwarded along
  375.    a particular SDRP route.  Associated with each set of criteria is a
  376.    set of one or more SDRP routes which should be used to route matching
  377.    packets.  The exact nature of the criteria is a local matter.  The
  378.    only restriction this document places on the applicability of SDRP
  379.    routes is that an IP datagram that contains a strict source route
  380.    should not be forwarded along an SDRP route.
  381.  
  382.    If the BR decides to forward the datagram along a particular SDRP
  383.    route, the BR constructs the SDRP packet by placing the original
  384.    datagram into the Payload field of the SDRP packet and constructing
  385.    the SDRP header based on the selected SDRP route.  The Next Hop
  386.    pointer is set to 0 (the first entry in the Source Route field of the
  387.    SDRP packet).  The value of the Time To Live field in the payload
  388.    header should be copied into the BR Hop Count field of the SDRP
  389.    header.
  390.  
  391.    The source address field in the delivery header should contain an IP
  392.    address of the BR. The value of the Don't Fragment flag of the
  393.    delivery header is copied from the Don't Fragment flag of the payload
  394.    header.  The value of the Type Of Service field in the delivery
  395.    header is copied from the Type Of Service field in the payload
  396.    header.  If the payload header contains an IP security option, that
  397.    option is replicated as an option in the delivery header.  All other
  398.    IP options in the payload header must be ignored.
  399.  
  400.    If the selected SDRP route is a loose source route, then the BR
  401.    consults the BGP or IDRP path table to find a path to the next hop
  402.    AS.  The BR chooses one such path, then selects one of the NLRI
  403.    associated with this path.  This prefix and its length are placed in
  404.    the Prefix and Prefix Length fields of the SDRP header.  If IDRP is
  405.    used, then the TOS corresponding to this route is copied into the TOS
  406.    field in the delivery header.  Subsequent BRs will use this prefix to
  407.    look up the next BGP or IDRP hop, thereby preventing hop-by-hop
  408.    routing loops along the loose source route.
  409.  
  410.    In essence, when a BR along a loose source route selects an NLRI
  411.    prefix, it is selecting a single route to the next hop AS, and
  412.    forcing subsequent BR's along the path to choose the same path.  Once
  413.    the BGP or IDRP delivers the packet to this next-hop AS, SDRP
  414.    continues forwarding it along the rest of the source route.
  415.  
  416.    The resulting SDRP packet is then forwarded as described in Section
  417.    5.2.2.
  418.  
  419.    If a BR decides to forward a datagram along a particular SDRP route,
  420.    and the payload header has Don't Fragment flag set to 1, and the
  421.    length of the datagram is greater than the MTU associated with the
  422.    SDRP route (if the MTU is defined), the BR should generate the ICMP
  423.    Destination Unreachable message with a code meaning "fragmentation
  424.    needed and DF set" in accordance with ([6]).  The BR should discard
  425.    the original datagram.
  426.  
  427.    If a BR has learned an MTU for a particular SDRP route, either via
  428.    ICMP messages or via configuration information, and it determines
  429.    that an SDRP packet must be fragmented before transmission, then it
  430.    must first fragment the payload packet using normal IP fragmentation.
  431.    SDRP packets are then constructed for each fragment, as describe
  432.    above.
  433.  
  434.    A BR may use the SDRP packets originated by the BR to verify the
  435.    feasibility of its SDRP routes. To do this the BR sets the value of
  436.    the Probe Indicator field in the SDRP packet to 1.  Receipt of an
  437.    SDRP control packet by the originating BR with the "Probe Completed"
  438.    Notification Code (see Section 7.1) indicates feasibility of the SDRP
  439.    route.  Persistent lack of SDRP control packets with the "Probe
  440.    Completed" Notification Code should be used as an indication that the
  441.    associated SDRP route is unfeasible.
  442.  
  443.  
  444. 5 Processing SDRP packets
  445.  
  446.  
  447.    We say that a BR receives an SDRP packet if the destination address
  448.    field in the delivery header of the packet arriving at the BR
  449.    contains one of the IP addresses of the BR.
  450.  
  451.    When a BR receives an SDRP packet, the BR extracts the Source Route
  452.    Protocol field from the SDRP header. Processing of an SDRP packet
  453.    with the value of the Source Route Protocol field other than 1 is
  454.    outside the scope of this document. If the value of this field is 1,
  455.    the BR should proceed as follows.
  456.  
  457.  
  458. 5.1 Supporting Transit Policies
  459.  
  460.  
  461.    A BR may be able to verify that a packet that it is given to forward
  462.    does not violate any of the transit policies, if any, of the domain
  463.    to which the BR belongs.  Specific verification mechanisms are a
  464.    matter that is local to the BR and are outside the scope of this
  465.    document.
  466.  
  467.    The only restriction on the verification mechanisms is that they may
  468.    take into account only the contents of the SDRP header, the payload
  469.    header, and transport protocol header of the payload packet.
  470.  
  471.    If the BR detects that the SDRP packet violates a domain's transit
  472.    policy it sends back an SDRP control packet and discards the
  473.    violating packet.
  474.  
  475.    SDRP control packets are not subject to transit policies.
  476.  
  477.    If a BR does not discard an SDRP packet due to a transit policy
  478.    violation, then the BR attempts to forward it as specified in Section
  479.    5.2.
  480.  
  481.    With SDRP a domain may enforce its transit policies by applying
  482.    filters based on the information present in the IP Header. For
  483.    example a BR may initially filter out all SDRP traffic from all
  484.    possible sources. A filter that allows certain SDRP traffic from
  485.    selected sources to pass through the BR could then be installed
  486.    dynamically as a result of a local check on a packet. Once a packet
  487.    passes the check against local transit policies, the appropriate
  488.    filter is installed into the forwarding database to allow subsequent
  489.    packets to pass through.  Thus, by caching appropriate filtering
  490.    information, a transit domain can efficiently enforce transit
  491.    policies.  Other transit policy enforcement mechanisms and
  492.    implementation techniques are not precluded by this document.
  493.  
  494.  
  495. 5.2 Forwarding SDRP packets
  496.  
  497.  
  498.    Procedures for forwarding of an SDRP packet depend on
  499.  
  500.    whether the BR has the routing information needed to forward the
  501.    packet; whether the SDRP route has been completely traversed or not;
  502.    whether the SDRP route is strict or loose, and whether the packet is
  503.    data or control.
  504.  
  505.    When forwarding an SDRP packet (either data or control) a BR should
  506.    not modify the following fields in the delivery header:
  507.  
  508.    Source Address Don't Fragment flag
  509.  
  510.  
  511.  
  512. 5.2.1 Forwarding algorithm pseudo-code
  513.  
  514.    The following pseudo-code gives an overview of the SDRP forwarding
  515.    algorithm.  Please consult the text below for more details.
  516.  
  517.    Let LOCAL_DI be the DI of the domain of the local system, NEXT_DI be
  518.    the next DI in the source route (or undefined if the source route has
  519.    been completed), and let NEXT_HOP be the IP address of the next hop
  520.    BR (as found in the D-FIB) if the packet is forwarded using SDRP.  We
  521.    say that NEXT_DI is adjacent if the local domain is adjacent to the
  522.    domain that has NEXT_DI as its DI.  Normal IP forwarding refers to
  523.    forwarding that can be accomplished using FIBs constructed via BGP,
  524.    IDRP or one or more IGPs.
  525.  
  526.      if the packet is a control packet begin
  527.        if the Target Border Router equals an address assigned to the
  528.    local BR
  529.          begin
  530.          remove the delivery header
  531.          process information carried in the control packet
  532.          return
  533.        else
  534.          if the packet can be forwarded using normal IP forwarding begin
  535.            set Next Domain Pointer to Source Route Length
  536.            forward the packet using normal IP forwarding
  537.            return
  538.          end if
  539.        end if
  540.      end if
  541.  
  542.      if the version field is not 1 begin
  543.        if the packet is a data packet begin
  544.          generate a control packet with "Unimplemented SDRP version"
  545.        end if
  546.        discard the packet
  547.        return
  548.      end if
  549.  
  550.      if the packet is a data packet begin
  551.        decrement the BR Hop Count field
  552.        if the BR Hop Count field is 0 begin
  553.          generate a control packet with "BR Hop Count Exceeded"
  554.          discard the data packet
  555.          return
  556.        end if
  557.        if the packet violates transit policy begin
  558.          generate a control packet with "Transit Policy Violation"
  559.          discard the data packet
  560.          return
  561.        end if
  562.      end if
  563.  
  564.      if the source route has not been completed begin
  565.        while the NEXT_DI is equal to the LOCAL_DI begin
  566.          update the value of the Next Domain Pointer field
  567.          set NEXT_DI to the next DI in the source route
  568.          if the source route is loose and NEXT_DI is not equal to the
  569.    LOCAL_DI         begin
  570.            select a BGP or IDRP route with a path that includes NEXT_DI
  571.            copy the NLRI from the route to the Prefix Length and Prefix
  572.            if it was an IDRP route, set appropriate TOS in delivery
  573.    header
  574.          end if
  575.        end while
  576.      end if
  577.  
  578.      if the source route has not been completed begin
  579.        if there is no route to NEXT_DI begin
  580.          if the packet is a data packet begin
  581.            generate a control packet with "No Route Available"
  582.          end if
  583.          discard the packet
  584.          return
  585.        end if
  586.        if the source route is strict and NEXT_DI is not adjacent begin
  587.          generate a control packet with "Strict Source Route Failed"
  588.          discard the packet
  589.          return
  590.        end if
  591.        if the source route is loose begin
  592.          select the routing infomation matching the Prefix field
  593.          if the routing information was an aggregate formed locally
  594.    begin
  595.            select a BGP or IDRP route with a path that includes NEXT_DI
  596.            copy the NLRI from the route to the Prefix Length and Prefix
  597.            if it was an IDRP route, set appropriate TOS in delivery
  598.    header
  599.          end if
  600.        end if
  601.        set NEXT_HOP from the routing information for NEXT_DI
  602.        route packet to NEXT_HOP using normal IP forwarding
  603.      else
  604.        if the packet is a data packet begin
  605.          remove the delivery header and the SDRP Header
  606.          if there is no normal IP route to the payload destination begin
  607.            generate a control packet with "No Route Available"
  608.            discard the packet
  609.            return
  610.          end if
  611.          forward the payload using normal IP forwarding
  612.          if the probe bit is set begin
  613.            generate a control packet with "Probe Completed"
  614.          end if
  615.        else
  616.            discard the control packet
  617.        end if
  618.      end if
  619.  
  620.  
  621. 5.2.2 Handling an SDRP control packet.
  622.  
  623.  
  624.    An SDRP control packet is indicated by 0 in the Data packet/Control
  625.    packet bit in the Flags field in the SDRP Header.
  626.  
  627.    If the Target Border Router field of the received SDRP packet
  628.    contains an IP address that is assigned to an interface attached to
  629.    the local system, then the local system should use the information
  630.    carried in the Notification Code field, the Source Route Identifier
  631.    field and the information carried in the Payload field to update the
  632.    status of its SDRP routes. Details of such procedures are described
  633.    in Section 7.
  634.  
  635.    Otherwise, the local systems checks whether it can forward the packet
  636.    to the BR specified in the Target Border Router field by using the
  637.    routing information present in its local FIB. If forwarding is
  638.    possible then the local system sets the destination address of the
  639.    delivery header to the address specified in the Target Border Router
  640.    field, and hands the packet off for normal IP forwarding.  If normal
  641.    IP forwarding is impossible then the packet may be forwarded in the
  642.    same manner as an SDRP data packet (described below) but with the
  643.    following exceptions.
  644.  
  645.    Control packets do not carry a BR Hop Count, which is neither
  646.    referenced nor decremented when forwarding.  Control packets are not
  647.    subject to transit policies.  If the version field of a control
  648.    packet is not understood, no control packet should be generated.  If
  649.    the source route is complete and the packet still cannot be forwarded
  650.    via normal IP routing, the packet should be dropped.
  651.  
  652.  
  653. 5.2.3 Handling an SDRP data packet.
  654.  
  655.  
  656.    An SDRP data packet is indicated by a one in the Data packet/Control
  657.    packet bit in the Flags field in the SDRP Header.
  658.  
  659.    An SDRP data packet is forwarded by sending the packet along the
  660.    source route in the SDRP Header.  When the source route is complete,
  661.    the payload may be removed from the data packet and forwarded
  662.    normally.  Further details are described below.
  663.  
  664.  
  665. 5.2.3 Checking the SDRP version number
  666.  
  667.  
  668.    An SDRP packet  that has a version number other than 1 should be
  669.    discarded.  If the SDRP packet was a data packet, then a control
  670.    packet with the Notification Code "Unimplemented SDRP version" should
  671.    be generated as specified in section 6.
  672.  
  673.  
  674. 5.2.4 Decrementing and checking BR Hop Count
  675.  
  676.  
  677.    If an SDRP data packet is to be forwarded, the BR Hop Count field
  678.    should be decremented.  If the resulting value is zero, then a
  679.    control packet with the Notification Code "BR Hop Count Exceeded"
  680.    should be generated as specified in section 6, and the packet should
  681.    be discarded.  The payload of the control packet should carry the
  682.    payload header followed by 64 bits of the payload data of the data
  683.    packet.
  684.  
  685.  
  686. 5.2.5 Enforcing transit policies
  687.  
  688.  
  689.    A BR may examine any data packet to verify if it complies with local
  690.    transit policies, as described in section 5.1.  If the verification
  691.    fails, the BR generates a control packet.  If the verification
  692.    referred to only the contents of the SDRP header, then the payload
  693.    field of the control packet should be empty. If the verification
  694.    referred to both the contents of the SDRP header and the payload
  695.    header, then the payload field of the control packet should carry the
  696.    payload header.  If the verification referred to transport protocol
  697.    header, then the payload field of the control packet should carry the
  698.    payload header and the transport header.
  699.  
  700.    The Notification Code field of the SDRP header in the control packet
  701.    is set to Transit Policy Violation.  The procedures for constructing
  702.    the rest of the SDRP Header of the control packet are specified in
  703.    Section 6.
  704.  
  705.  
  706. 5.2.6 Incomplete source routes
  707.  
  708.  
  709.    If a BR receives an SDRP packet with an incomplete source route, the
  710.    BR extracts the DI of the next domain from the Source Route field.
  711.    The BR locates the high-order byte of the appropriate DI by using the
  712.    Next Domain Pointer field as an offset relative to the start of the
  713.    Source Route field.  If the extracted DI of the next domain is the
  714.    same as the DI of the local domain, then the Next Domain Pointer
  715.    should be incremented by two (the size of a DI).
  716.  
  717.    If the source route is still incomplete, then this procedure should
  718.    be repeated until either the source route is complete, or the
  719.    extracted DI is not the same as the DI of the local system.  If upon
  720.    the termination of the procedure the source route becomes complete,
  721.    see section 5.2.9.  If the Next Domain Pointer has been advanced as a
  722.    result of this section, then the BR must consult its D-FIB and select
  723.    a route with a path which includes the extracted DI.  The NLRI for
  724.    this route should be copied into the Prefix Length and Prefix fields.
  725.  
  726.    Otherwise, the local BR proceeds as follows.
  727.  
  728.  
  729. 5.2.6.1 Finding a route to the next domain
  730.  
  731.  
  732.    Given the DI of the next domain, the BR next consults its D-FIB.  If
  733.    the source route is loose, then the BR should use the information
  734.    carried in the Prefix and Prefix Length as an index into its BGP or
  735.    IDRP routing table.  If it finds a matching route then it must select
  736.    the corresponding D-FIB entry.  If the route was formed locally by
  737.    aggregation, then the BR must consult its D-FIB and select any route
  738.    with a path which includes the extracted DI.  The NLRI for this route
  739.    should be copied into the Prefix Length and Prefix fields.
  740.  
  741.    Otherwise, if no entry exists in the D-FIB for the next domain, then
  742.    the packet should be discarded.  If the packet was a data packet, a
  743.    control message with Notification Code "No Route Available" should be
  744.    generated as specified in Section 6. No other actions are necessary.
  745.  
  746.    If there is a D-FIB entry, the BR next examines the packet to
  747.    determine if the packet specified a strict source route.  If so, and
  748.    the next domain is not adjacent to the local domain, then a control
  749.    packet with the Notification Code "Strict Source Route Failed" should
  750.    be generated as specified in section 6 and the original packet should
  751.    be discarded.  No other actions are necessary.
  752.  
  753.    The D-FIB entry includes the IP address of the next SDRP-speaking BR
  754.    to which the SDRP packet should be routed.  The destination address
  755.    in the delivery header is replaced by this address.  The resulting
  756.    packet can then be forwarded using normal IP forwarding.
  757.  
  758.  
  759. 5.2.6.2 Last Hop Optimization
  760.  
  761.    A small optimization can be performed if there is only a single DI in
  762.    the source route that has not been traversed.  In this case, if there
  763.    is a route in the FIB for the destination address of the payload
  764.    packet, and the next DI in the source route indicates an adjacent
  765.    domain, and the FIB route passes through this domain, then the source
  766.    route may be considered complete and processing may proceed as in
  767.    section 5.2.7.
  768.  
  769.  
  770. 5.2.7 Completed source routes
  771.  
  772.  
  773.    If the SDRP packet received by a BR with a completed source route is
  774.    a control packet and if the Target Border Router field carries an IP
  775.    address assigned to the BR, then the packet should be processed as
  776.    specified in Section 7.  Otherwise, if the SDRP packet is a control
  777.    packet, and the packet cannot be forwarded via either SDRP or normal
  778.    IP forwarding and the packet should be dropped.
  779.  
  780.    If the packet is an SDRP data packet received by a BR, then the
  781.    payload packet may be extracted from the SDRP packet.  The BR Hop
  782.    Count field should be copied from the SDRP header into the IP TTL
  783.    field in the payload header.  The resulting payload packet is then
  784.    forwarded using normal IP forwarding.  If there is no FIB entry for
  785.    the destination, then the packet should be discarded and a control
  786.    message with Notification Code "No Route Available" should be
  787.    generated as specified in Section 6.
  788.  
  789.    If the packet can be forwarded and if the Probe Indication bit is set
  790.    to one in the SDRP header, then a control message with Notification
  791.    Code "Probe Completed" should be generated as specified in section 6.
  792.    The payload of the control packet should carry the first 64 bits of
  793.    the SDRP header and the payload header.
  794.  
  795.  
  796. 6 Originating SDRP control packets
  797.  
  798.  
  799.    A BR sends a control packet in response to either error conditions,
  800.    or to successful completion of a probe request (indicated via Probe
  801.    Indication in the Flags field).
  802.  
  803.    The Data Packet/Control Packet field  is set to indicate Control
  804.    Packet.  The following fields are copied from the SDRP header of the
  805.    Data packet that caused the generation of the Control packet:
  806.  
  807.    Loose/Strict Source Route Source Route Protocol Type Source Route
  808.    Identifier Source Route Length field Payload Protocol Type
  809.  
  810.    A Control packet should not carry a Probe Indication field.
  811.  
  812.    The Target Border Router is copied from the source IP address of the
  813.    delivery header of the SDRP Data packet.
  814.  
  815.    The BR generating a control packet checks its FIB for a route to the
  816.    destination depicted by the Target Border Router field.  If such a
  817.    route is present, then the value of the Destination Address field in
  818.    the delivery header is set to the Target Border Router, the Source
  819.    Address field in the delivery header is set to the IP address of one
  820.    of the interfaces attached to the local system, and the packet is
  821.    forwarded via normal IP forwarding.
  822.  
  823.    If the FIB does not have a route to the destination depicted by the
  824.    Target Border Router field, the local system constructs the Source
  825.    Route field of the Control packet by reversing the SDRP route carried
  826.    in the Source Route field of the Data packet, sets the value of the
  827.    Next Hop Pointer to the value of the Source Route Length field minus
  828.    the value of the Next Hop Pointer field of the SDRP data packet that
  829.    caused generation of the Control Packet.
  830.  
  831.    The contents of the Payload field depends on the reason for
  832.    generating a control packet.
  833.  
  834.    The resulting packet is then handled via SDRP Forwarding procedures
  835.    described in Section 5.2.
  836.  
  837.  
  838.  
  839.  
  840.  
  841. 7. Processing control information
  842.  
  843.  
  844.    A BR participating in SDRP may receive control information in two
  845.    forms, SDRP control packets from other BRs and ICMP messages from
  846.    routers that do not participate in SDRP, but are involved in
  847.    forwarding SDRP packets.
  848.  
  849.  
  850. 7.1 Processing SDRP control packets
  851.  
  852.  
  853.    If after processing an SDRP control packet a BR determines that the
  854.    packet carries information about SDRP routes used by the BR, the BR
  855.    may use the information in the SDRP control packet to select
  856.    alternate routes if available and to mark the affected routes as
  857.    unfeasible.
  858.  
  859.    To correlate information carried in the SDRP control packet with the
  860.    SDRP routes used by the BR, the BR uses information carried in the
  861.    SDRP header of the control packet and optionally in the SDRP payload
  862.    of the control packet (if present).
  863.  
  864.    In general receipt of any SDRP control packet that carries one of the
  865.    following Notification Codes
  866.  
  867.    No Route Available Strict Source Route Failed Unimplemented SDRP
  868.    version
  869.  
  870.    indicates that the corresponding SDRP route is presently not feasible
  871.    and thus should not be used for packet forwarding.  The BR may at
  872.    some later point attempt to use an SDRP route that was marked as
  873.    infeasible.
  874.  
  875.    Receipt of an SDRP control packet that carries the "Transit Policy
  876.    Violation" Notification Code shall be interpreted as follows:
  877.  
  878.    If the control packet carries no payload data then the corresponding
  879.    SDRP route violates transit policy regardless of the content of the
  880.    payload packet carried along that route.  If the control packet
  881.    carries only the payload header, then the corresponding SDRP route
  882.    violates transit policy due to the content of the payload header.  If
  883.    the control packet carries the payload header and the transport
  884.    header, then the corresponding SDRP route violates transit policy for
  885.    a particular combination of the contents of the payload and transport
  886.    headers.
  887.  
  888.    Receipt of an SDRP control packet that carries "Probe Completed"
  889.    Notification Code  indicates that the corresponding SDRP route is
  890.    feasible.
  891.  
  892.    If a BR receives an SDRP control packet that carries "BR Hop Count
  893.    Exceeded" Notification Code, the BR should use the information in the
  894.    payload of the Control packet to construct an ICMP Time Exceeded
  895.    Message with code "time to live exceeded in transit" and send the
  896.    message to the host indicated by the source address in the Payload
  897.    Header.
  898.  
  899.  
  900.  
  901. 7.2 Processing ICMP messages
  902.  
  903.  
  904.    To correlate information carried in the ICMP messages with the SDRP
  905.    routes used by the BR, the BR uses the last 4 octets of the ICMP
  906.    message.  These bytes carry the Source Route Identifier of the SDRP
  907.    route used by the BR.
  908.  
  909.    ICMP Destination Unreachable messages with a code meaning
  910.    "fragmentation needed and DF set" should be used for SDRP MTU
  911.    discovery as described in Section 9.
  912.  
  913.    All other ICMP Unreachable messages indicate that the associated
  914.    route is infeasible.
  915.  
  916.  
  917. 8. Constructing D-FIBs.
  918.  
  919.  
  920.    A BR constructs its D-FIB as a result of participating in either BGP
  921.    or IDRP. A BR must advertise via BGP or IDRP a route to destinations
  922.    within its domain to all of its external peers (BRs in adjacent
  923.    domains). A BR may also advertise (via BGP or IDRP) to its external
  924.    peers routes to destinations within other domains, but are installed
  925.    in the BR's D-FIB.
  926.  
  927.    If a BR receives a route to an adjacent domain from a BR in that
  928.    domain and selects that route as part of its BGP or IDRP Decision
  929.    Process, then it must propagate this route (via BGP or IDRP) to all
  930.    other BRs within its domain.  A BR may also propagate such a route if
  931.    it depicts an autonomous system other than the adjacent domain.
  932.  
  933.  
  934. 9. SDRP MTU Discovery
  935.  
  936.  
  937.    To participate in Path MTU Discovery ([6]) a BR may maintain
  938.    information about the maximum length of the payload packet that can
  939.    be carried without fragmentation along a particular SDRP route.
  940.  
  941.    SDRP provides two complimentary techniques to support MTU Discovery.
  942.  
  943.    The first one is passive and is based on the receipt of the ICMP
  944.    Destination Unreachable messages (as described in Section 7.2).  By
  945.    combining information provided in the ICMP message with local
  946.    information about the SDRP route the local system can determine the
  947.    length of a payload packet that would require fragmentation.
  948.  
  949.    The second one is active and employs the Probe Indicator bit.  If an
  950.    SDRP data packet that carries the Probe Indicator bit in the SDRP
  951.    header and Don't Fragment flag in the delivery header triggers the
  952.    last BR on the SDRP route to return an SDRP Control packet (with the
  953.    Notification Code "Probe Completed"), then the information carried in
  954.    the payload header of the control packet can be used to determine the
  955.    length of the payload packet that went through the SDRP route without
  956.    fragmentation.
  957.  
  958.  
  959.  
  960.  
  961. References
  962.  
  963.  
  964.  
  965.    [1] Lougheed, K., and Y. Rekhter, "A Border Gateway Protocol 3 (BGP-
  966.    3),
  967.        RFC 1267, cisco Systems, T.J. Watson Research Center, IBM
  968.        Corp., October 1991.
  969.  
  970.    [2] Rekhter, Y., and P. Gross, "Application of the Border Gateway
  971.        Protocol in the Internet", RFC 1268, T.J. Watson Research Center,
  972.        IBM Corp., ANS, October 1991.
  973.  
  974.    [3] Y. Rekhter and T. Li, "A Border Gateway Protocol 4 (BGP-4)",
  975.        Internet Draft, cisco Systems, T.J. Watson Research Center, IBM
  976.        Corp., September 1992.
  977.  
  978.    [4] S. Hares, "IDRP for IP", Internet Draft, NSFNET/MERIT, June 1992
  979.  
  980.    [5] Postel, J., "Internet Protocol - DARPA Internet Program Protocol
  981.        Specification", RFC 791, DARPA, September 1981.
  982.  
  983.    [6] J. Mogul, S., and S. Deering, "Path MTU Discovery", RFC1191,
  984.        November 1990
  985.  
  986.  
  987.  
  988.